package cn.z2huo.leetcode.problem.NO_0003;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 给定一个字符串，找出不含有重复字符的最长子串的长度。
 *
 * 示例：
 * 给定 "abcabcbb" ，没有重复字符的最长子串是 "abc" ，那么长度就是3。
 * 给定 "bbbbb" ，最长的子串就是 "b" ，长度是1。
 * 给定 "pwwkew" ，最长子串是 "wke" ，长度是3。请注意答案必须是一个子串，"pwke" 是 子序列 而不是子串。
 *
 * 在暴力法中遇到了一个坑，开始时判断字符在子串中是否重复，如果重复则更新result的值
 * 这样当遇到aab这种情况时，i=1，j=2时，判断b在a子串中是否重复；之后可能就不会判断ab中是否有重复字符了，
 * 这样的话，最大长度就停留在了1，而实际情况是2。
 * 改进措施是，判断字符在子串中是否重复，当不重复时，更新result的值；当重复时就跳过当前循环，
 * 因为继续扩大子串的范围就没有意义了，子串中已经出现了重复字符
 *
 * 作者： 张一卓
 * 时间： 2019/12/25 19:25
 */
class Solution2 {

    /**
     * 暴力法
     * 需要遍历指定字符串，不断扩大子串的范围，在这个过程中判断扩大子串指针处的字符是否在当前子串中已经存在，
     * 如果存在则跳过当前循环，因为子串中已经出现重复字符，没有必要继续向下找其他的重复字符了，
     * 之后更新子串的起始位置，重新向后遍历字符串来扩大子串的范围，直到遇到重复字符为止。
     *
     * 这样其实会重复判断一些东西，比如bacda，头指针开始位置为0，遍历到第二个a后，更新头指针为1，重新遍历，又遍历到第二个a，
     * 这样一个包含重复字符的子串acda就判断了两次。
     *
     * 并且判断重复字符时还需要一层循环，这样的话，就需要三层循环。
     *
     * @param s 给定字符串
     * @return  返回字符串s的不含重复字符的最长子串的长度
     */
    public int lengthOfLongestSubstring(String s) {
        int result = 0;
        // 判断字符串是否为空，当为空时，返回结果为 0
        if (s == null || "".equals(s)) {
            return 0;
        }
        // 循环遍历字符串
        for (int i = 0; i < s.length(); i++) {
            for (int j = i+1; j <= s.length(); j++) {
                // 当某个子串中的最后一个字符在子串中重复时，跳过当前循环，继续扩大子串的范围就没有意义了，因为子串中已经出现了重复字符
                if (isRepeat(s.substring(i,j))) {
                    break;
                }else {
                    // 如果不重复时，将result和j-i中更大的赋值给result，相当于更新了不重复子串的最大长度
                    result = Math.max(j-i, result);
                }
            }
        }
        return result;
    }

    /**
     * 判断字符串的最后一个字符是否重复
     * @param string    给定字符串
     * @return  boolean 如果重复则为true，如果不重复则为false
     */
    public boolean isRepeat(String string) {

        boolean contains = string.substring(0, string.length() - 1).contains(string.substring(string.length() - 1));
        return contains;

//        int count = 0;
//        char c = string.charAt(string.length()-1);
//        for (int i = 0; i < string.length(); i++) {
//            if (string.charAt(i) == c) {
//                count ++;
//            }
//        }
//        return count > 1;
    }

    /**
     * 滑动窗口
     * 我感觉滑动窗口与暴力法的区别在于，后者有很多子串都需要进行重复判断，而滑动窗口可以避免一些重复情况的判断。
     * 比如，bacda，头指针为0，遍历指针向后移动，当定位到第二个a时，发现在bacd中有重复，就改变头指针的位置为1，这时遍历指针位置不变，
     * 再次判断a在acd中仍然重复，头指针位置变为2，再次判断a在cd中是否重复，不重复，之后遍历指针向后移动。继续判断
     *
     * 这样就避免了暴力法中一个重复子串判断多次的情况。
     * @param s 给定字符串
     * @return  返回字符串s的不含重复字符的最长子串的长度
     */
    public int lengthOfLongestSubstring2(String s) {
        int result = 0;
        int i = 0, j = 0;
        // set用来存放字符
        // abcabcbb
        // bdacaefgh
        // bcaad
        Set<Character> set = new HashSet<>();
        while (i < s.length() && j < s.length()) {
            // 当set中包含当前j遍历字符时，从set中移除i位置的字符，之后增加i，j不变，直到set中没有当前j遍历的字符时
            if (set.contains(s.charAt(j))) {
                set.remove(s.charAt(i++));
            }else {
                // 当set中不包含当前j遍历字符时，将该处的字符添加到set中，并更新result的值
                set.add(s.charAt(j++));
                result = Math.max(j - i, result);
            }
        }
        return result;
    }

    // abcabcbb
    // abcdbcbb
    public int lengthOfLongestSubstring3(String s) {
        int result = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0, j = 0; j < s.length(); j++) {
            if (map.containsKey(s.charAt(j))) {
                result = Math.max(j - i, result);
                i++;
            }
            map.put(s.charAt(j), j);
        }
        return result;
    }
//    public int lengthOfLongestSubstring3(String s) {
//        int n = s.length(), ans = 0;
//        Map<Character, Integer> map = new HashMap<>(); // current index of character
//        // try to extend the range [i, j]
//        for (int j = 0, i = 0; j < n; j++) {
//            if (map.containsKey(s.charAt(j))) {
//                i = Math.max(map.get(s.charAt(j)), i);
//            }
//            ans = Math.max(ans, j - i + 1);
//            map.put(s.charAt(j), j + 1);
//        }
//        return ans;
//    }
}
